package Offer;

/*
    给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
    每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的
    最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时
    得到的最大乘积是18。
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/jian-sheng-zi-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */

/*
    思路:
        就是将一个数拆成几个数之和，让他们的乘积最大
        怎么才能让乘积最大？

* */
public class T14_cuttingRope {

    public static void main(String[] args) {

    }

    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];  //dp[i]表示整数i拆分成至少2个数之后，得到的最大乘积
        // 由于0和1都不能拆，所以dp[0]和dp[1]都是0，而其他dp值还没求出来之前的初始值也是0

        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));//curMax 记录当前最大值
            }
            dp[i] = curMax;//每一轮循环都能得到关于i的最大乘积，它能为后面做参考
        }
        return dp[n];
    }
}